package com.leetcode.partition14;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author `RKC`
 * @date 2021/10/15 9:22
 */
public class LC1334阈值距离内邻居最少的城市 {

    private static final int INF = Integer.MAX_VALUE >> 2;

    public static int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int answer = 0;
        //记录城市i开始在规定范围内能到达的城市数量
        int[] cityToCount = new int[n];
        for (int i = 0; i < n; i++) {
            cityToCount[i] = bellmanFord(n, i, edges, distanceThreshold);
        }
        //根据边构建无向图的邻接矩阵
//        int[][] matrix = new int[n][n];
//        for (int[] edge : edges) {
//            matrix[edge[0]][edge[1]] = edge[2];
//            matrix[edge[1]][edge[0]] = edge[2];
//        }
        //从每个城市出发，计算距离内的邻居城市个数
//        for (int i = 0; i < n; i++) {
////            cityToCount[i] = dijkstra(i, matrix, distanceThreshold);
//            cityToCount[i] = bellmanFord(i, matrix, distanceThreshold);
//        }
        int temp = INF;
        //从后往前遍历，保证相同数量的情况下编号最大
        for (int i = cityToCount.length - 1; i >= 0; i--) {
            if (temp > cityToCount[i]) {
                temp = cityToCount[i];
                answer = i;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
//        int[][] edges = {{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}};
//        int n = 4, distanceThreshold = 4;
//        int[][] edges = {{0, 1, 2}, {0, 4, 8}, {1, 2, 3}, {1, 4, 2}, {2, 3, 1}, {3, 4, 1}};
//        int n = 5, distanceThreshold = 2;
//        int[][] edges = {{0, 1, 1}};
//        int n = 2, distanceThreshold = 7422;

        int[][] edges = {{0, 1, 2}, {0, 4, 8}, {1, 2, 3}, {1, 4, 2}, {2, 3, 1}, {3, 4, 1}};
        int n = 5, distanceThreshold = 2;
        System.out.println(findTheCity(n, edges, distanceThreshold));
    }

    private static int bellmanFord(int n, int start, int[][] edges, int distanceThreshold) {
        int count = 0;
        int[] distances = new int[n];
        Arrays.fill(distances, INF);
        distances[start] = 0;
        //n个顶点最多经过n-1次松弛
        for (int i = 1; i <= n - 1; i++) {
            boolean isRelaxation = false;
            for (int[] edge : edges) {
                int dis = distances[edge[0]] + edge[2];
                if (distances[edge[1]] > dis && dis <= distanceThreshold) {
                    distances[edge[1]] = dis;
                    isRelaxation = true;
                }
                dis = distances[edge[1]] + edge[2];
                if (distances[edge[0]] > dis && dis <= distanceThreshold) {
                    distances[edge[0]] = dis;
                    isRelaxation = true;
                }
            }
            if (!isRelaxation) break;
        }
        System.out.println(Arrays.toString(distances));
        for (int dis : distances) {
            if (dis == INF || dis == 0) continue;
            count++;
        }
        return count;
    }

    private static int bellmanFord(int start, int[][] matrix, int distanceThreshold) {
        int count = 0;
        int[] distances = new int[matrix.length];
        Arrays.fill(distances, INF);
        distances[start] = 0;

        for (int k = 1; k <= matrix.length - 1; k++) {
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (i == j || matrix[i][j] == 0) continue;
                    int dis = distances[i] + matrix[i][j];
                    if (distances[j] > dis && dis <= distanceThreshold) {
                        distances[j] = dis;
                    }
                }
            }
        }
        for (int dis : distances) {
            if (dis == INF || dis == 0) continue;
            count++;
        }
        System.out.println(Arrays.toString(distances));
        return count;
    }

    private static int dijkstra(int start, int[][] matrix, int distanceThreshold) {
        int count = 0;
        int[] distances = new int[matrix.length];
        Arrays.fill(distances, INF);
        distances[start] = 0;
        //优先队列      {(vertex, distances, retainDistance), ...}
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[1], o2[1]));
        minHeap.offer(new int[]{start, 0, distanceThreshold});
        while (!minHeap.isEmpty()) {
            int[] neighbor = minHeap.poll();
            int nearestIndex = neighbor[0], distance = neighbor[1], retain = neighbor[2];
            //不能继续往下走，跳过当前节点
            if (retain <= 0) continue;
            //以start为起点，nearestIndex为中转点，更新到其余所有点的距离
            for (int i = 0; i < matrix.length; i++) {
                if (matrix[nearestIndex][i] <= 0) continue;
                int dis = distance + matrix[nearestIndex][i];
                if (dis < distances[i] && retain - matrix[nearestIndex][i] >= 0) {
                    minHeap.offer(new int[]{i, dis, retain - matrix[nearestIndex][i]});
                    distances[i] = dis;
                }

            }
        }
        for (int dis : distances) {
            if (dis == INF || dis == 0) continue;
            count++;
        }
        System.out.println(start + "开始");
        System.out.println(Arrays.toString(distances));
        return count;
    }
}
